package GreedyAlgorithmPackage;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class merge_ {
  @Test
  public void mergeTest(){
    int[][] intervals = new int[][]{{1,3},{2,6},{8,10},{15,18}};
    int[][] merge = merge(intervals);
    for (int[] point : merge) {
      StringBuilder sb = new StringBuilder();
      sb.append(point[0]).append(",").append(point[1]);
      System.out.println(sb.toString());
    }

  }

  // 注意区间的left也要移动
  public int[][] merge(int[][] intervals) {
    List<int[]> result = new ArrayList<>();
    Arrays.sort(intervals, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        return Integer.compare(o1[0],o2[0]);
      }
    });
    int left = intervals[0][0];
    int right = intervals[0][1];
    for (int i = 1; i < intervals.length ; i++){
      if (intervals[i][0] > right){
        result.add(new int[]{left,right});
        left = intervals[i][0];
        right = intervals[i][1];

      }
      else{
        right = Math.max(right,intervals[i][1]);
      }
    }
    // 到最后也要添加区间
    result.add(new int[]{left,right});
    // 将集合转为数组
    return result.toArray(new int[result.size()][]);
  }
}
